#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>

using namespace std;

//Ориентированный взвешенный граф. NameType - тип уникального идентификатора вершины, 
//WightType - тип веса, обычно - double
template <typename NameType, typename WeightType>
class CGraph {
public:
    typedef NameType CVertexNameType;
    typedef WeightType CEdgeWeightType;
	
	struct CVertex {
		map <NameType, WeightType> outgoing, incoming;
	};
	
	map <NameType, CVertex> vertices;
	
	//Итератор рёбер
    class CEdgeIterator {
	public:
		bool inverse;
		NameType vertex;
		typename map <NameType, WeightType> :: iterator it;
		//Следующий элемент - можно заменить на оператор++
        void Next(){
			it++;
		}
        bool operator==( const CEdgeIterator& other ){
			return vertex == other.vertex && it == other.it;
		}
        //Текущее ребро: имя начальной и конечной вершины дуги
        pair<NameType, NameType> CurrentEdge(){
			if(inverse){
				return make_pair(it->first, vertex);
			}
			return make_pair(vertex, it->first);
		}
        //Вес текущего ребра
        WeightType CurrentWeight(){
			return it->second;
		}
    };
    //Диапазон исходящих из вершины дуг
    pair<CEdgeIterator, CEdgeIterator> GetOutgoingArcs( NameType v ){
		typename map <NameType, CVertex> :: iterator iter = vertices.find(v);
		CEdgeIterator begin;
		begin.inverse = false;
		begin.vertex = v;
		begin.it = iter->second.outgoing.begin();
		CEdgeIterator end;
		end.inverse = false;
		end.vertex = v;
		end.it = iter->second.outgoing.end();
		return make_pair(begin, end);
	}
    //Диапазон всходящих в вершину дуг
    pair<CEdgeIterator, CEdgeIterator> GetIncomingArcs( NameType v ){
		typename map <NameType, CVertex> :: iterator iter = vertices.find(v);
		CEdgeIterator begin;
		begin.inverse = true;
		begin.vertex = v;
		begin.it = iter->second.incoming.begin();
		CEdgeIterator end;
		end.inverse = true;
		end.vertex = v;
		end.it = iter->second.incoming.end();
		return make_pair(begin, end);
	}
    //Итератор вершин
    class CVertexIterator {
	private:
		typename map <NameType, CVertex> :: iterator it;
    public:
        //Следующий элемент - можно заменить на оператор++
        void Next(){
			it++;
		}
        bool operator==( const CEdgeIterator& other ){
			return it == other.it;
		}
        //Текущая вершина
        NameType CurrentVertex(){
			return it->first;
		}
    };
    //Все вершины
    pair<CVertexIterator, CVertexIterator> GetAllVertexes(){
		CVertexIterator begin;
		begin.it = vertices.begin();
		CVertexIterator end;
		end.it = vertices.end();
		return make_pair(begin, end);
	}
    //Добавление/удаление
    bool AddVertex( NameType v ){
		if(vertices.find(v) != vertices.end()){
			return false;
		}
		vertices[v];
	}
    bool DeleteVertex( NameType v ){
		typename map <NameType, CVertex> :: iterator iter = vertices.find(v);
		if(iter == vertices.end()){
			return false;
		}
		for(typename map <NameType, WeightType> :: iterator it = iter->second.outgoing.begin(); it != iter->second.outgoing.end(); it++){
			vertices[it->first].incoming.erase(v);
		}
		for(typename map <NameType, WeightType> :: iterator it = iter->second.incoming.begin(); it != iter->second.incoming.end(); it++){
			vertices[it->first].outgoing.erase(v);
		}
		vertices.erase(iter);
		return true;
	}
    bool AddEdge( NameType v, NameType u, WeightType weight ){
		typename map <NameType, CVertex> :: iterator iter_v = vertices.find(v);
		if(iter_v == vertices.end()){
			return false;
		}
		if(iter_v->second.outgoing.find(u) != iter_v->second.outgoing.end()){
			return false;
		}
		typename map <NameType, CVertex> :: iterator iter_u = vertices.find(u);
		if(iter_u == vertices.end()){
			return false;
		}
		iter_v->second.outgoing[u] = weight;
		iter_u->second.incoming[v] = weight;
		return true;
	}
    bool DeleteEdge( NameType v, NameType w ){
		typename map <NameType, CVertex> :: iterator iter = vertices.find(w);
		if(iter == vertices.end()){
			return false;
		}
		if(iter->second.outgoing.find(w) == iter->second.outgoing.end()){
			return false;
		}
		iter->second.outgoing.erase(w);
		iter = vertices.find(w);
		iter->second.incoming.erase(v);
		return true;
	}
    //Очистка
    void DeleteAll(){
		vertices.clear();
	}
};

//Алгоритм Дейкстры. Возвращает вес кратчайшего пути от startVertex до endVertex в графе graph
template<class GraphType>
typename GraphType::CEdgeWeightType Dijkstra( GraphType& graph, typename GraphType::CVertexNameType startVertex, 
    typename GraphType::CVertexNameType endVertex )
{
	map <typename GraphType::CVertexNameType, typename GraphType::CEdgeWeightType> d;
	set <pair <typename GraphType::CEdgeWeightType, typename GraphType::CVertexNameType> > s;
	d[startVertex] = 0;
	s.insert(make_pair(0, startVertex));
	while(!s.empty()){
		typename GraphType::CVertexNameType cur = (s.begin())->second;
		s.erase(s.begin());
		if(cur == endVertex){
			return d[cur];
		}
		pair <typename GraphType::CEdgeIterator, typename GraphType::CEdgeIterator> iters = graph.GetOutgoingArcs(cur);
		for(typename GraphType::CEdgeIterator it = iters.first; !(it == iters.second); it.Next()){
			typename GraphType::CEdgeWeightType cost = d[cur] + it.CurrentWeight();
			pair <typename GraphType::CVertexNameType, typename GraphType::CVertexNameType> edge = it.CurrentEdge();
			if(d.find(edge.second) == d.end() || cost < d[edge.second]){
				s.erase(make_pair(d[edge.second], edge.second));
				d[edge.second] = cost;
				s.insert(make_pair(cost, edge.second));
			}
		}
	}
	fprintf(stderr, "Path does not exist\n");
	exit(0);
}

template<class GraphType, typename HeuristicsType>
class CHeuristics {
public:
	map <typename GraphType::CVertexNameType, HeuristicsType> h;
	// для конструктора необходимо знать список вершин, т.е. нужно передать и сам граф
	// также для вершины должен существовать метод GetDist(), который возвращает расстояние между вершинами
    explicit CHeuristics( GraphType &graph, typename GraphType::CVertexNameType& endVertex ){
		pair <typename GraphType::CVertexIterator, typename GraphType::CVertexIterator> iters = graph.GetAllVertexes();
		for(typename GraphType::CVertexIterator it = iters.first; !(it == iters.second); it.Next()){
			h[it.CurrentVertex()] = endVertex.GetDist(it.CurrentVertex());
		}
	}
    //Получение значения эвристики
    HeuristicsType GetHeuristics( typename GraphType::CVertexNameType& vertex ){
		return h[vertex];
	}
};

//Алгоритм А*. Возвращает вес кратчайшего пути от startVertex до endVertex в графе graph с учётом эвристики
template<class GraphType>
typename GraphType::CEdgeWeightType AStarAlogithm( GraphType& graph, typename GraphType::CVertexNameType startVertex, 
    typename GraphType::CVertexNameType endVertex)
{
	CHeuristics <GraphType, typename GraphType::CEdgeWeightType> h(graph, endVertex);
	map <typename GraphType::CVertexNameType, typename GraphType::CEdgeWeightType> d;
	set <pair <typename GraphType::CEdgeWeightType, typename GraphType::CVertexNameType> > s;
	d[startVertex] = 0;
	s.insert(make_pair(h.GetHeuristics(startVertex), startVertex));
	while(!s.empty()){
		typename GraphType::CVertexNameType cur = (s.begin())->second;
		s.erase(s.begin());
		if(cur == endVertex){
			return d[cur];
		}
		pair <typename GraphType::CEdgeIterator, typename GraphType::CEdgeIterator> iters = graph.GetOutgoingArcs(cur);
		for(typename GraphType::CEdgeIterator it = iters.first; !(it == iters.second); it.Next()){
			typename GraphType::CEdgeWeightType cost = d[cur] + it.CurrentWeight();
			pair <typename GraphType::CVertexNameType, typename GraphType::CVertexNameType> edge = it.CurrentEdge();
			if(d.find(edge.second) == d.end() || cost < d[edge.second]){
				s.erase(make_pair(d[edge.second] + h.GetHeuristics(edge.second), edge.second));
				d[edge.second] = cost;
				s.insert(make_pair(cost + h.GetHeuristics(edge.second), edge.second));
			}
		}
	}
	fprintf(stderr, "Path does not exist\n");
	exit(0);
}

int main(){
	CGraph <int, int> g;
	g.AddVertex(1);
	g.AddVertex(2);
	g.AddEdge(1, 2, 1);
	g.DeleteEdge(1, 2);
	g.AddEdge(1, 2, 1);
	g.DeleteVertex(1);
	g.AddVertex(1);
	g.AddEdge(1, 2, 1);
	cout << Dijkstra(g, 1, 2) << endl;
	return 0;
}
